import java.util.Arrays;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/28 14:17
 * @description: 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 * <p>
 * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 * <p>
 * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
 * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
 * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * <p>
 * 必须 原地 修改，只允许使用额外常数空间。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 * <p>
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 * 示例 3：
 * <p>
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 * 首先从数组末尾开始查找，找到第一个比右边元素小的元素，记为位置 i。这是因为从 i+1 到末尾的元素是降序排列的，无法形成更大的排列，需要通过 i 位置的元素来寻找更大的排列。
 * 如果找到了这样的 i，再从数组末尾开始查找第一个比 nums [i] 大的元素，记为位置 j。交换 nums [i] 和 nums [j]，这样可以确保得到一个比原排列大的排列。
 * 交换后，i 位置右侧的元素仍然是降序排列的，我们需要将其反转成升序排列，以得到最小的可能值，这就是下一个更大的排列。
 * 如果没有找到这样的 i（即整个数组是降序排列），说明这是最大的排列，我们需要将其反转得到最小的排列（循环到最开始）。
 * 步骤 1：定位 “可调整的左边界”（i）
 * 从右向左遍历，找到第一个满足 nums[i] < nums[i+1] 的位置 i。
 * 例：在 [1,3,2,4,1] 中，i=2（因为 nums[2]=2 < nums[3]=4）。
 * 原理：
 * i 右侧的元素是降序排列（如 [4,1]），这部分无法通过内部调整变得更大（降序是局部最大排列）。
 * i 是左侧第一个 “可以被更大元素替换” 的位置，替换后整体序列会增大。
 * 步骤 2：找到 “最小的更大元素”（j）
 * 从右向左遍历 i 右侧的元素，找到第一个满足 nums[j] > nums[i] 的位置 j。
 * 例：i=2 时，右侧元素为 [4,1]，第一个大于 nums[2]=2 的是 nums[3]=4，即 j=3。
 * 原理：
 * 选择 i 右侧 “最小的更大元素”（而非最大的），确保替换后序列增幅最小（符合 “下一个” 的定义）。
 * 步骤 3：交换 i 和 j 的元素
 * 交换后序列变为 [1,3,4,2,1]。
 * 原理：
 * 替换 i 位置的元素为更大的值，使序列在 i 位置首次增大，且增幅最小。
 * 步骤 4：反转 i 右侧的元素
 * 交换后，i 右侧的元素仍是降序（如 [2,1]），将其反转成升序（如 [1,2]），最终序列为 [1,3,4,1,2]。
 * 原理：
 * 降序的右侧元素反转后变为升序，是该局部范围内的最小排列。这一步确保在 i 位置增大后，右侧元素尽可能小，从而整体序列是 “下一个” 更大的排列（而非更大的任意排列）。
 * 4. 特殊情况：当前是最大排列
 * 若序列是严格降序（如 [3,2,1]），则不存在 “下一个更大的排列”，此时需返回最小排列（反转整个序列，得到 [1,2,3]）。
 */
public class Solution31 {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        int j = nums.length - 1;
        if (i >= 0) {
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i+1, nums.length - 1);
    }

    public static void main(String[] args) {
        //[1,2,3]、[1,3,2]、[2,1,3]，[2,3,1] ，[3,1,2] [3,2,1]。
        //[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2][2,1,3,4]
        Solution31 solution = new Solution31();
        int[] nums = {3, 2, 1};
        solution.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
